package com.cloud.code.牛客网;

import java.util.*;

public class Test64 {

    public static void main(String[] args) {
        Permutation("abc");
    }

    static Set<String> set = new HashSet<>();
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();

        char[] chars = str.toCharArray();
        int length = chars.length;
        boolean[] used = new boolean[length];
        Deque<Character> stack = new ArrayDeque<Character>();

        dfs(chars,length,0,used,stack,res);

        return res;

    }

    private static void dfs(char[] chars, int length, int depth, boolean[] used, Deque<Character> stack, ArrayList<String> res) {

        if(length == depth){
            String string = Arrays.toString(new Deque[]{stack}).replaceAll("\\W+","");
            if(!set.contains(string)){
                res.add(string);
                set.add(string);
            }

            return;
        }

        for (int i = 0; i < length; i++) {

            if(used[i]){
                continue;
            }
            stack.addLast(chars[i]);
            used[i] = true;
            dfs(chars,length,depth+1,used,stack,res);
            used[i] = false;
            stack.removeLast();
        }


    }
}
